
/*
 * PriorityQueue.java
 * Software Engineering Lab 2
 * Oct 10, 2006
 * 
 * By:
 * Dan Grissom - grissodt@email.uc.edu
 * Jon Hoffman - hoffmaj1@email.uc.edu
 * Jon Nafziger - nafzigjw@email.uc.edu
 * Mike Schmidt - schmidm2@email.uc.edu
 * 
 * The Event class is used to store the priority and an informational string of an event.
 */

package priorityQueue;

// Includes Vectors
import java.util.Vector;

// Defines the Event Class

import events.Event;

/**
 * The PriorityQueue is used to determine the next {@link Event} that needs to
 * be processed. This data structure stores events based upon the time that they
 * occur from the lowest to the highest. The only Event that can be accessed
 * immediately is the event with the highest priority.
 * 
 * @author Team Switchboard Boxcar
 * 
 */
public class PriorityQueue
{
	private Vector<Event> myHeap;	// Defines the heap
	private int frontIndx;			// Defines pointer to front 
	private int  backIndx;			// Define pointer to back 

	/**
	 * PriorityQueue is the basic constructor of the PriorityQueue class.  
	 *
	 */
	public PriorityQueue()
	{
		myHeap = new Vector<Event>(0);
		frontIndx = 0;
		backIndx = 0;		
	};
	
	/**
	 * isEmpty is a boolean function that can be called to determine if the
	 * PriorityQueue is empty
	 * 
	 * @return Returns a boolean value. True = PriorityQueue is empty. False =
	 *         PriorityQueue is not empty.
	 */
	public boolean isEmpty() { return backIndx == 0;}
	
	/**
	 * peekTop returns the integer that represents the next event that needs to
	 * be processed by the priority queue.
	 * 
	 * @return An integer value representing the time that the event with the
	 *         highest priority occurs at.
	 */
	public int peekTop() {return myHeap.elementAt(frontIndx).GetTime();}
	
	/**
	 * enqueue is the function that is called to place another event in the
	 * queue. This function initially places the event at the back of the
	 * Priority Queue and then resorts the queue as necessary.
	 * 
	 * @param Input
	 *            Expects an Event to be input into the Priority Queue.
	 */
	public void enqueue(Event Input) 
	{
		//Verifies Input is Real Value
		if(Input == null)
			return;
		int tempIndx = backIndx;
		myHeap.add(backIndx,Input);
		backIndx++;
		
		//While Loop moves item from bottom to top of PriorityQueue
		while( 
			   ((tempIndx-1)/2 >= 0) &&
		       (myHeap.elementAt(tempIndx).GetTime() < 
		    	myHeap.elementAt((tempIndx-1)/2).GetTime())
		      )
		{
			swapEvents(tempIndx,(tempIndx-1)/2);
			tempIndx = ((tempIndx-1)/2);
			
		}
	};
	
	/**
	 * dequeue is the function that is called to remove the event with the
	 * highest priority (lowest time) from the Priority Queue.
	 * 
	 * @return Returns the event from the top of the priority queue.
	 */
	public Event dequeue() 
	{
		if(isEmpty())
			return null;
		
		// Creating Events that serve as value holders in Logic
		Event topValue;	
		//Event tempEvent = new Event();
				
		// Remove top value, make bottom value top of the heap
		topValue = myHeap.elementAt(frontIndx);
		myHeap.setElementAt(myHeap.elementAt(--backIndx), frontIndx);
		myHeap.remove(backIndx);
		
		
		int tempIndx = 0;
		while((2*(tempIndx+1) <= backIndx))	{
			if (myHeap.elementAt(tempIndx).GetTime() > myHeap.elementAt(
					2 * (tempIndx + 1) - 1).GetTime()) {
				if (2 * (tempIndx + 1) < backIndx) {
					if (myHeap.elementAt(2 * (tempIndx + 1) - 1).GetTime() < myHeap
							.elementAt(2 * (tempIndx + 1)).GetTime()) {
						swapEvents(2 * (tempIndx + 1) - 1, tempIndx);
						tempIndx = 2 * (tempIndx + 1) - 1;
					} else {
						swapEvents(2 * (tempIndx + 1), tempIndx);
						tempIndx = 2 * (tempIndx + 1);
					}
				} else {
					swapEvents(2 * (tempIndx + 1) - 1, tempIndx);
					tempIndx = 2 * (tempIndx + 1) - 1;
				}

			}

			else 
				if( 2*(tempIndx+1) < backIndx)
				{	
					if( myHeap.elementAt(tempIndx).GetTime() >
						myHeap.elementAt(2*(tempIndx+1)).GetTime())
					{
						swapEvents(2*(tempIndx+1), tempIndx);
						tempIndx = 2*(tempIndx+1);											
					} else break;
				}else break;
		}
		return (Event)(topValue);
	}

	/**
	 * swapEvents swaps two events in the Priority Queue. This function should
	 * never be called from outside of the Priority Queue.
	 * 
	 * @param Index1
	 *            The integer index of the first item to be swaped.
	 * @param Index2
	 *            The integer index of the second item to be swaped.
	 */
	private void swapEvents(int Index1, int Index2) 
	{
		Event swapEvent = myHeap.elementAt(Index1);
		myHeap.setElementAt((myHeap.elementAt(Index2)), Index1);
		myHeap.setElementAt((swapEvent),Index2);
	}
}
